package leetcode.code1383;

import java.util.Arrays;
import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
		Integer[] ids = new Integer[n];
		for (int i = 0; i < ids.length; i++) {
			ids[i] = i;
		}
		Arrays.sort(ids, (a, b) -> efficiency[b] - efficiency[a]);
		long sum = 0, ans = 0;
		int p = 0;
		PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> speed[a] - speed[b]);
		while (p < k) {
			int id = ids[p];
			sum += speed[id];
			queue.add(id);
			p++;
		}
		ans = sum * efficiency[ids[p - 1]];
		while (p < n) {
			int id = ids[p];
			int spd = speed[id], eff = efficiency[id];
			if (speed[queue.peek()] < spd) {
				int poll = queue.poll();
				sum -= speed[poll];
				sum += spd;
				queue.add(id);
				ans = Math.max(ans, sum * eff);
			}
			p++;
		}
		return (int) (ans % mod);
	}

	@Override
	public void debug4() {
		H.compare(72, this.maxPerformance(6, H.str2array3("[2,10,3,1,5,8]"), H.str2array3("[5,4,3,9,7,2]"), 4));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
